<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,200分)- 报文解压缩（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<ul><li>为了提升数据传输的效率&#xff0c;会对传输的报文进行压缩处理。</li><li>输入一个压缩后的报文&#xff0c;请返回它解压后的原始报文。</li><li>压缩规则&#xff1a;n[str]&#xff0c;表示方括号内部的 str 正好重复 n 次。</li><li>注意 n 为正整数&#xff08;0 &lt; n &lt;&#61; 100&#xff09;&#xff0c;str只包含小写英文字母&#xff0c;不考虑异常情况。</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入压缩后的报文&#xff1a;</p> 
<p>1&#xff09;不考虑无效的输入&#xff0c;报文没有额外的空格&#xff0c;方括号总是符合格式要求的&#xff1b;</p> 
<p>2&#xff09;原始报文不包含数字&#xff0c;所有的数字只表示重复的次数 n &#xff0c;例如不会出现像 5b 或 3[8] 的输入&#xff1b;</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>解压后的原始报文</p> 
<p>注&#xff1a;原始报文长度不会超过1000&#xff0c;不考虑异常的情况</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td>输入</td><td>3[k]2[mn]</td></tr><tr><td>输出</td><td>kkkmnmn</td></tr><tr><td>说明</td><td>k 重复3次&#xff0c;mn 重复2次&#xff0c;最终得到 kkkmnmn</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td>输入</td><td>3[m2[c]]</td></tr><tr><td>输出</td><td>mccmccmcc</td></tr><tr><td>说明</td><td>m2[c] 解压缩后为 mcc&#xff0c;重复三次为 mccmccmcc</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题可以使用栈结构解题。思路也比较简单明了。</p> 
<p></p> 
<p>我们只需要统计出如下几个关键信息即可&#xff1a;</p> 
<ul><li>要被重复的子串&#xff08;可以分解记录子串两边的&#39;[&#39;&#xff0c;&#39;]&#39;的位置&#xff09;</li><li>要被重复的子串的重复次数</li></ul> 
<p></p> 
<p>定义一个栈stack&#xff0c;然后开始遍历输入字符串str的每一个字符c&#xff1a;</p> 
<ul><li>如果 c &#61;&#61; &#39;[&#39;&#xff0c;则可以统计到两个信息&#xff1a;</li></ul> 
<ol><li>要被重复的子串的起始位置</li><li>根据题目描述&#xff0c;&#39;[&#39;的前面必然是重复次数&#xff0c;因此&#39;[&#39;可以作为重复次数结束统计的标志</li></ol> 
<ul><li>如果 c &#61;&#61; &#39;]&#39;&#xff0c;则可以得到要被重复的子串的结束位置&#xff0c;此时我们可以进行生成解压串&#xff0c;来替换掉对应范围的压缩串</li><li>如果 c 是数字&#xff0c;则必然是重复次数的组成&#xff0c;此时可以记录下来&#xff0c;当遇到’[‘时&#xff0c;可以得到一个重复次数</li><li>如果 c 是其他字符&#xff0c;则压入栈中。</li></ul> 
<p></p> 
<h4>JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on(&#34;line&#34;, (line) &#61;&gt; {
  console.log(getResult(line));
});

/* 算法逻辑 */
function getResult(str) {
  const stack &#61; [];

  // idxs记录要被重复的子串的起始位置
  const idxs &#61; [];
  // nums记录要被重复的子串的重复次数&#xff0c;和idxs对应
  const nums &#61; [];

  // tmpRepeatCount记录正在拼接的重复次数字符串
  const tmpRepeatCount &#61; [];

  // 遍历输入的字符串, c是当前正在遍历的字符
  for (let c of str) {
    if (c &#61;&#61; &#34;[&#34;) {
      // 此时tmpRepeatCount已记录完当前重复子串对应的重复次数的所有字符
      const repeatCount &#61; Number(tmpRepeatCount.join(&#34;&#34;));
      nums.push(repeatCount);
      tmpRepeatCount.length &#61; 0;

      // 记录要被重复的子串的起始位置
      idxs.push(stack.length);
    } else if (c &#61;&#61; &#34;]&#34;) {
      // 需要被重复的子串在栈中的起始位置
      const start &#61; idxs.pop();
      // 需要被重复的次数
      const repeatCount &#61; nums.pop();
      // 需要被重复的子串
      const repeatStr &#61; stack.splice(start).join(&#34;&#34;);

      // 将新串压入栈中
      stack.push(new Array(repeatCount).fill(repeatStr).join(&#34;&#34;));
    } else if (c &gt;&#61; &#34;0&#34; &amp;&amp; c &lt;&#61; &#34;9&#34;) {
      tmpRepeatCount.push(c);
    } else {
      stack.push(c);
    }
  }

  return stack.join(&#34;&#34;);
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);
    String str &#61; sc.nextLine();
    System.out.println(getResult(str));
  }

  public static String getResult(String str) {
    // Java可以使用StringBuilder模拟栈
    StringBuilder sb &#61; new StringBuilder();

    // idxs记录要被重复的子串的起始位置
    LinkedList&lt;Integer&gt; idxs &#61; new LinkedList&lt;&gt;();
    // nums记录要被重复的子串的重复次数&#xff0c;和idxs对应
    LinkedList&lt;Integer&gt; nums &#61; new LinkedList&lt;&gt;();
    // tmpRepeatCount记录重复次数的的字符组成
    StringBuilder tmpRepeatCount &#61; new StringBuilder();

    // 遍历输入的字符串
    for (int i &#61; 0; i &lt; str.length(); i&#43;&#43;) {
      // c是当前正在遍历的字符
      char c &#61; str.charAt(i);

      if (c &#61;&#61; &#39;[&#39;) {
        // 此时tmpRepeatCount已记录完当前重复子串对应的重复次数的所有字符
        int repeatCount &#61; Integer.parseInt(tmpRepeatCount.toString());
        nums.add(repeatCount);
        tmpRepeatCount &#61; new StringBuilder();

        // 记录要被重复的子串的起始位置
        idxs.add(sb.length());
      } else if (c &#61;&#61; &#39;]&#39;) {
        // 需要被重复的子串在栈中的起始位置
        int start &#61; idxs.removeLast();
        // 需要被重复的次数
        int repeatCount &#61; nums.removeLast();
        // 需要被重复的子串
        String repeatStr &#61; sb.substring(start);

        // 重复后的新串
        StringBuilder tmp &#61; new StringBuilder();
        for (int j &#61; 0; j &lt; repeatCount; j&#43;&#43;) tmp.append(repeatStr);

        // 替换对应子串为重复后的新串
        sb.replace(start, sb.length(), tmp.toString());
      } else if (c &gt;&#61; &#39;0&#39; &amp;&amp; c &lt;&#61; &#39;9&#39;) {
        tmpRepeatCount.append(c);
      } else {
        sb.append(c);
      }
    }

    return sb.toString();
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
s &#61; input()


# 算法入口
def getResult(s):
    stack &#61; []

    # idxs记录要被重复的子串的起始位置
    idxs &#61; []
    # nums记录要被重复的子串的重复次数&#xff0c;和idxs对应
    nums &#61; []

    # tmpRepeatCount记录重复次数的的字符组成
    tmpRepeatCount &#61; []

    # 遍历输入的字符串&#xff0c;c是当前正在遍历的字符
    for c in s:
        if c &#61;&#61; &#39;[&#39;:
            # 此时tmpRepeatCount已记录完当前重复子串对应的重复次数的所有字符
            repeatCount &#61; int(&#34;&#34;.join(tmpRepeatCount))
            nums.append(repeatCount)
            tmpRepeatCount &#61; []

            # 记录要被重复的子串的起始位置
            idxs.append(len(stack))
        elif c &#61;&#61; &#39;]&#39;:
            # 需要被重复的子串在栈中的起始位置
            start &#61; idxs.pop()
            # 需要被重复的次数
            repeatCount &#61; nums.pop()
            # 需要被重复的子串
            repeatStr &#61; &#34;&#34;.join(stack[start:])

            # 先删除要被替换的子串&#xff0c;然后加入新串&#xff08;即重复对应次数的子串&#xff09;
            stack &#61; stack[:start]
            stack.append(&#34;&#34;.join([repeatStr] * repeatCount))
        elif &#39;0&#39; &lt;&#61; c &lt;&#61; &#39;9&#39;:
            tmpRepeatCount.append(c)
        else:
            stack.append(c)

    return &#34;&#34;.join(stack)


# 算法调用
print(getResult(s))
</code></pre> 
<p></p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>